package 动态规划.背包And分组And切割问题系列;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/6/19 15:43
 */
public class leetcode1262可被3整除的最大和 {


    /*
     这是个思维题！， 如果
     能明白这个 取模 之间的关系， 那其实 状态转移就很好写了！

    -
    这个题的 依赖关系，还真的不太好理解！

     f（i， mod） ： 表示的是 从 i ~ len 结尾时， 在余数 为mod 的时候 能被 3 整除的最大和！
     状态转移确实 不太好整：
     x % 3  就三个取值， 0， 1， 2 如果 x % = 0 ，这个就不说了， 直接累加就行了
     x % 3 = 1 的话， 需要 加上 x % 3 =2 的值， 就可以使 累加和 又能被  3 整除了
     大致的就是这个原理！


     进阶版：
     - 对这个题， 进行改变一下， 不是对 3 整除， 而是对 k整除？
     - 如果 nums 有 负数存在的话， 这个 dp 还是否正确？

     */


    public int function(int index,int mod,int nums[]){
        if(index == nums.length){
            /*
             到达 end 的时候， 如果余数 mod ！= 0 说明当前的 路径和， 不能被 3 整除， 直接返回一个
             对结果没有影响的 值就行了， 因为此时，nums【i】 全都是整数， 那直接返回一个最小值就可以了！
             */
            return mod == 0 ? 0 : Integer.MIN_VALUE;
        }
        // 决策
        int ans = 0;
        if(nums[index] % 3 == 0 ){ // || mod = 0 这个 条件写在这里不太合适， 因为 初始的 时候 传入的条件 ，就是 mod = 0
            ans = function(index +  1,mod,nums) + nums[index];
        }else{
            // 选 或者 不选 当前元素
            // 选的话， 依赖 , 需要进行重新 取模一下， 就是重新计算下 mod 的值
            ans = function(index + 1,(nums[index] % 3 + mod) % 3,nums) + nums[index];

            // 不选的依赖 , 去 最优值
            ans = Math.max(ans, function(index + 1,mod,nums));
        }
        /*
            这种写法：
            return  Math.max(function(index + 1,mod,nums), function(index + 1,(nums[index] % 3 + mod) % 3,nums) + nums[index]);
            直接 把  nums【index】 %  3 == 0 的这种情况 ， 不做特判了，
            其实这样也是正确的因为， 这种情况 最后肯定是 会走选择的情况的！

         */
        return ans;
    }










    /*
     暴力的做法， 像这种，递归的写法， 根本就没法优化！
     */
    private int max = 0;
    public void recursion(int index,int sum,int nums[]){
        if(index == nums.length){
            if(sum % 3 == 0){
                max = Math.max(max,sum);
            }
            return ;
        }
        recursion(index + 1,sum + nums[index],nums);
        recursion(index + 1,sum,nums);

    }


}
